The present invention relates to a packet switch for allotting a packet input through an input line to an output line.
Recently, with the fast spread of Internet in the world, the amount of communications traffic of lines has remarkably increased, and a high and large capacity packet switch has been earnestly demanded. Normally, the configurations of buffers realizing packet switches can be roughly grouped into output buffers, shared buffers, cross point buffers, and input buffers. From a viewpoint of throughput, packet switches using output buffers and shared buffers have conventionally been used for general purpose. However, a line speed has become higher and higher with number lines increased, and a packet switch using an input buffer having a relatively low memory access speed has been re-evaluated. For example, a memory access speed of the packet switch using the output buffer is N+1 (N indicates the number of lines) times as fast as the line speed. The memory access speed of the packet switch using a shared buffer is 2N times as fast as the line speed. On the other hand, the memory access speed of the packet switch using the input buffer is 2 times as fast as the line speed, that is, lower than the speeds of the packet switches using the output buffers, the shared buffers, etc.
Although it is known that, in the packet switch using the input buffer, the throughput is normally reduced down to 58.6% by the HOL (Head of Line) blocking, it is also know that 100% throughput can be attained by logically separating the FIFO in the input buffer for each output buffer.
The packet switch using a cross point buffer has almost the same characteristic in memory access speed and throughput as the packet switch using the input buffer. However, since it requires a buffer for each cross point, N×N buffers are required when the number of input lines and output lines is N each, thereby resulting in large hardware.
FIG. 28 shows the configuration of a conventional packet switch using an input buffer. It shows the configuration for realizing a multicast function of copying a packet input through an input line to a plurality of output lines. The configuration has been suggested in ‘KR. Ahuja, B. Prabhakar and N. Mckeown, “Multicast scheduling for input-queued switches”, IEEE J. Selected Areas Com., May 1996.’
The packet switch shown in FIG. 28 is provided with an input buffer having a unicast (UC) queue and a multicast (MC) queue. A packet read from the MULTICAST queue is copied in a crossbar switch, and transmitted to a plurality of output lines.
FIG. 29 shows another configuration of the conventional packet switch having the input buffer. The configuration has been suggested by ‘Naoki Matsuoka et al., “A Study on Multicast Structure for Input Queued Switches”, The Institute of Electronics, Information, and Communication Engineers, B-6-65, 1999.’
The packet switch shown in FIG. 29 has the same configuration as the packet switch shown in FIG. 28 in that the input buffer has a unicast queue and a multicast queue, but is different a multicast packet is copied in each input buffer and output to each output line.
However, in the conventional packet switch shown in FIG. 28, a scheduler provided for each input buffer, or a scheduler shared among a plurality of input buffers has to control the conflict among the output lines to which a multicast packet has to be copied for all input buffers in one unit time. Therefore, the conflict control is complicated, and causes the problem of a heavy load of the process. As a result, the conventional packet switch is not appropriate as a high-speed and large-capacity packet switch for processing a large number of conflicting lines in a short unit time.
Furthermore, in the conventional packet switch shown in FIG. 29, a multicast packet is copied in each input buffer. Accordingly, there are a large number of packets actually transmitted and received. As a result, the input rate of the multicast packets is low, and it becomes difficult to quickly perform processes.